Міністерство освіти і науки України Національний університет «Львівська політехніка»
Лабораторна робота №4 з дисципліни: «Технології розподілених систем та паралельних обчислень» Варіант - 6
Тема роботи: Розподілене програмування на основі технології Cilk.
Завдання: Знаходження шляху на графі з допомогою алгоритму Лі.
Виконання.
Код програми:
#include <iostream>
#include <string>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>
#include <dos.h>
#include <windows.h>
#include <cilk.h>
#include <cilk_stub.h>
#include <reducer_opadd.h>
#include <stdio.h>
using namespace std;
using namespace cilk;
#define FALSE 0
#define TRUE 1
#define NROWS 6
#define MCOLS 6
// Symbols:
// '.' = open
// '#' = blocked
// 'S' = start
// 'G' = goal
// '+' = path
// 'x' = bad path
char maze[NROWS][MCOLS] = {
{ 'S', '.', '.', '.', '#', '#' },
{ '#', '.', '#', '.', '.', '.' },
{ '#', '.', '#', '#', '.', '#' },
{ '.', '.', '#', '.', '#', '#' },
{ '#', '.', '.', '.', '#', 'G' },
{ '#', '.', '#', '.', '.', '.' }
};
void display_maze(void);
int find_path(int x, int y);
int main(void)
{
clock_t t = clock();
display_maze();
if (find_path(0, 0) == TRUE)
printf("Success!\n");
else
printf("Failed\n");
display_maze();
int i;
cin >> i;
clock_t t1 = clock();
cout << "TIME: " << (t1 - t) / 1000 << "ms" << endl;
system("pause");
return 0;
}
// main()
void display_maze(void)
{
int i;
printf("MAZE:\n");
cilk_for (i = 0; i < NROWS; i++)
printf("%.*s\n", MCOLS, maze[i]);
printf("\n");
return;
}
int find_path(int x, int y)
{
if (x < 0 || x > MCOLS - 1 || y < 0 || y > NROWS - 1) return FALSE;
if (maze[y][x] == 'G') return TRUE;
if (maze[y][x] != '.' && maze[y][x] != 'S') return FALSE;
maze[y][x] = '+';
if (find_path(x, y - 1) == TRUE) return TRUE;
if (find_path(x + 1, y) == TRUE) return TRUE;
if (find_path(x, y + 1) == TRUE) return TRUE;
if (find_path(x - 1, y) == TRUE) return TRUE;
maze[y][x] = 'x';
return FALSE;
}// find_path()
Програма в роботі:
Без використання Cilk:
/
З використанням Cilk:
/
Висновок: на лабораторній роботі було виконано завдання написавши код, який реалізовує алгоритм його виконання. Замість пошуку шляху на графі з використанням алгоритму лубі, використав алгоритм лі. В досліді декілька раз виконав запуск програми з mpi і без. По результатах видно, що з використанням
cilk працює швидше. Хоча опрацьовувались не велика кількість даних, але отримано результат.
